package LeetCode.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/8/8
 * @Description:1749. 任意子数组和的绝对值的最大值
 */
public class maximum_absolute_sum_of_any_subarray {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, -5, 1, -4, 3, -2};
        System.out.println(solution.maxAbsoluteSum1(nums));
    }

    static class Solution {
        /*贪心+分类讨论*/
        public int maxAbsoluteSum(int[] nums) {
            int len = nums.length;
            //正数和，负数和，正数和最大，负数和最大
            int positiveT = 0, negativeT = 0, positiveM = 0, negativeM = 0;
            //对正负数分别讨论就行了
            for (int num : nums) {
                positiveT += num;
                positiveM = Math.max(positiveM, positiveT);
                positiveT = Math.max(0, positiveT);
                negativeT += num;
                negativeM = Math.min(negativeM, negativeT);
                negativeT = Math.min(0, negativeT);
            }
            return Math.max(positiveM, -negativeM);
        }

        //        方法二：前缀和
        /*由于子数组和等于两个前缀和的差，那么取前缀和中的最大值与最小值，它俩的差就是答案。

        如果最大值在最小值右边，那么算的是最大子数组和。

        如果最大值在最小值左边，那么算的是最小子数组和的绝对值（相反数）。*/
        public int maxAbsoluteSum1(int[] nums) {
            //贪心 + 前缀和思想
            int sum = 0, max = 0, min = 0;
            for(int val : nums)
            {
                sum += val;
                if(sum > max) max = sum;
                else if(sum < min) min = sum;
            }
            return max - min;
        }
    }
}
